package com.cqs.leetcode.dp;

/**
 * @author lixiaowen
 * @create 2019-12-28
 */
public class MinimumPathSum64 {

    //DP
    static class Solution {
        public int minPathSum(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            int[][] result = new int[grid.length][grid[0].length];
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (i == 0) {
                        if (j == 0) result[0][0] = grid[0][0];
                        else {
                            result[0][j] = result[i][j - 1] + grid[i][j];
                        }
                    } else if (j == 0) {
                        result[i][j] = result[i - 1][j] + grid[i][j];
                    } else {
                        result[i][j] = Math.min(result[i][j - 1], result[i - 1][j]) + grid[i][j];
                    }
                }
            }
            return result[grid.length - 1][grid[0].length - 1];
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            int[][] test = {{1,3,1},{1,5,1},{4,2,1}};
            int minPath = solution.minPathSum(test);
            System.out.println(minPath);
        }
    }

}
